---
id: 散列表
title: 散列表
---


散列表也叫作哈希表(hash table)，这种数据结构提供了键(Key)和值 (Value)的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时 间复杂度接近于O(1)。



- 散列表的基本原理
    散列表在本质上也是一个数组。可是数组只能根据下标，像a[0]、a[1]、a[2]、a[3]、 a[4]这样来访问，而散列表的Key则是以字符串类型为主的。  
    所以我们需要一个“中转站”，通过某种方式，把Key和 数组下标进行转换。这个中转站就叫作哈希函数。  
    在不同的语言中，哈希函数的实现方式是不一样的


由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过 哈希函数获得的下标有可能是相同的。例如002936这个Key对应的数组下标是2; 002947这个Key对应的数组下标也是2。  
这种情况，就叫作哈希冲突。  


解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。  
开放寻址法的原理很简单，当一个Key通过哈希函数获得对应的数组下标已被占 用时，我们可以“另谋高就”，寻找下一个空档位置。